package com.wushijia.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author Administrator
 * @date 2021-06-15 11:36
 */
public class InsertionSort {

  public static void main(String[] args) {
    int[] arr = {4, 1, 6, 9, 10, 22, 1, 7, 8, 100};

//    for (int i = 1; i < arr.length; i++) {
//      int j = i;
//
//      while (j > 0 && arr[j] < arr[j - 1]) {
//        swap(arr, j, j - 1);
//        j--;
//      }
//      System.out.println(Arrays.toString(arr));
//    }

    insertSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));

  }

  //Arrays.sort
  private static void insertSort(int[] a, int left, int right) {
    for (int i = left, j = i; i < right; j = ++i) {
      int ai = a[i + 1];
      while (ai < a[j]) {
        a[j + 1] = a[j];
        if (j-- == left) {
          break;
        }
      }
      a[j + 1] = ai;
    }
  }

  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}
